
/**

解法
问题场景已经很清晰了，我们这里套用公式来完成动态规划算法的分析的实现。

首先，我们需要分析出什么是子决策，子决策是针对一系列对象进行的相同类型的决定，在背包问题中，子决策应该是每一次操作都是决定是否将某一个物品放入背包。

其次，我们需要确定该问题状态量到底是什么，前文提到，归纳的节点是状态，前面的分析中“前1个，前2个...前n个物体分别放入0-V的背包中的最大价值”是归纳的节点，我们就用f[i][v]表示将前i个物品放入容积为v的背包的最大价值

然后，我们需要判断如何得到最优物理量，在背包问题中，f[n][V]就是我们的目标

接着，根据已知的内容判断初始状态：当不放物品或者背包为0时，价值一定为0

最后，我们考虑写出状态转移方程，状态方程就是我们上面两个定理分析得到的归纳过程：f[n][V] = max{f[n-1][V], f[n-1][V-w[n]]+va[n]}

编写代码时，只需要两个循环即可完成

for(int i = 1; i < n+1; ++i){ // 依次确定不同决策后不同状态的选优值
    for(int j = 0; j < V+1; ++j){ // 对第i次决策过程，确定不同状态的选优值
        f[i][j] = max{f[i-1][j], f[i-1][j-w[i]]+va[i]};
    }
}
return f[n][V];


 */




/***
问题：
有一堆石头，每块石头的重量都是正整数。

每次从中选出任意两块石头，然后将它们一起粉碎。
假设石头的重量分别为 x 和 y，且 x≤y。那么粉碎的可能结果如下：
如果 x 与 y 相等，那么两块石头都会被完全粉碎；
否则，重量为 x 的石头将会完全粉碎，而重量为 y 的石头的新重量为 y−x。

最后，最多只会剩下一块石头。返回此时石头最小的可能重量。如果没有石头剩下，就返回 0。
**/


/***
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

 

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

题目不必多说，两块石头相撞，找出剩下最小的。虽然看似给了很多石头，其实我们可以将其分类融合成两块石头，使这两块石头质量尽可能的相近。

显然最小的答案是0，也就是说两个石头一样的重，为sumWeight / 2。那么我们现在开始尝试寻找最接近sumWeight /2的一些石头的集合。

到了石头堆面前，我们手头现在有一个sum/2大小的背包，现在要想办法尽可能的将背包装满。

现在开始装石头。

拿到石头后我们有两种选择，1：装，2：不装。这可能是废话。

那么装或者不装是有判断依据的，满足条件了我们才会去装石头。

装石头的判断依据显然是让背包越满越好，然而可能我们装入了石头后，反而还不如之前不装满，这就需要我们继续思考了。

这就会有新旧两种状态的矛盾。

新状态是指装石头，旧状态是指不装石头。

还有一个概念是最优解，是说在目前为止，你的背包里面装了选择最优策略所得到的石头，也就是说你的背包里装了目前为止所能拿到的最多的石头。

那么新旧两种状态要去比较必然需要都同时处于最优解才可以进行比较。

而很显然，旧的状态是已经达到最优解得了。

那么我们需要让新状态也达到最优解。

既然已经放入了当前石头，那么也就意味着要让背包剩下的空间达到最优解。这也意味着我们需要重新去寻找剩余空间的最优解。

不过不用担心，剩余空间的最优解我们已经在dp数组中已经存储了，我们只需要去查看就可以。

dp数组是一个大小为背包大小的数组，每个数组空间都存储了对应下标大小的最优解。也就是要用空间换时间的算法，将前面计算过的最优解

存储下来。

对于我们拿到的每一块石头我们都要去对每一个可以容纳下它的背包去进行最优解更新，这样我们dp数组的每一个空间才能保证都是最优解。
 */

public class  {

    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int n = sum >> 1;
        int[] f = new int[n + 1];
        for (int stone : stones) {
            for (int i = n; i >= stone; --i) {
                f[i] = Math.max(f[i], f[i - stone] + stone);
            }
        }
        return sum - 2 * f[n];
    }
}


public Solution (){

    public int dp(int[] w,int[] v, int N,int W){

        int[][] dp=new int[N+1][W+1];


        //初始化状态
        for(int i=0 ; i<N; i++){
            dp[i][0] = 0;
        }
        for(int j=0;j<W;j++){
            dp[0][j] = 0;
        }

        for(int tn = 1; tn < N+1 ; tn++){ // 遍历每一件物品
            for(int rw =1;rw < W+1;rw++){ //背包容量有多大就还要计算多少次
               if(rw < w[tn]){ 
                // 当背包容量小于第tn件物品重量时，只能放入前tn-1件
                dp[tn][rw] = dp[tn-1][rw];
               } else{
                // 当背包容量还大于第tn件物品重量时，进一步作出决策 
                dp[tn][rw] = Math.max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]);
               }
            }
        }

    return dp[N][W];
    }

}
